package com.leetcode.partition10;


import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/9/7 8:53
 */
public class LC968监控二叉树 {

    private static final int N = 1010, INF = 0x3f3f3f3f;
    private static int id = 0, index = 0;
    private static int[] head = new int[N];
    //dp[i][0]：i节点不放摄像头，但是能被父节点监控  dp[i][1]：i节点不放摄像头，至少能被一个子节点监控  dp[i][2]：i节点放置摄像头
    private static int[][] dp = new int[N][3], element = new int[N][2];

    public static int minCameraCover(TreeNode root) {
        //对于每一个节点u来说有三种情况，1：被父节点监控  2：自己装上一个监控  3：被子节点v监控
        if (root.left == null && root.right == null) return 1;
        for (int i = 0; i < N; i++) head[i] = -1;
        createGraph(root);
        dfs(root.val);
        return Math.min(dp[root.val][1], dp[root.val][2]);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0, new TreeNode(0, new TreeNode(0), new TreeNode(0)), null);
        System.out.println(minCameraCover(root));
    }

    private static void dfs(int u) {
        dp[u][2] = 1;
        int sum = 0;
        for (int i = head[u]; i != -1; i = element[i][1]) {
            int v = element[i][0];
            dfs(v);
            //当前位置不放摄像头，但是被父节点监控，此时u的子节点v可以放，也可以不放，但v要被v的子节点监控
            dp[u][0] += Math.min(dp[v][2], dp[v][1]);
            //当前位置放置摄像头，子节点三种情况都可以，我们取最小
            dp[u][2] += Math.min(dp[v][0], Math.min(dp[v][1], dp[v][2]));
            sum += Math.min(dp[v][1], dp[v][2]);
        }
        dp[u][1] = INF;
        for (int i = head[u]; i != -1; i = element[i][1]) {
            int v = element[i][0];
            dp[u][1] = Math.min(dp[u][1], dp[v][2] + sum - Math.min(dp[v][1], dp[v][2]));
        }
    }

    private static void createGraph(TreeNode root) {
        if (root == null) return;
        root.val = id++;
        createGraph(root.left);
        createGraph(root.right);
        if (root.left != null) createEdge(root.val, root.left.val);
        if (root.right != null) createEdge(root.val, root.right.val);
    }

    private static void createEdge(int u, int v) {
        int[] curr = element[index];
        curr[0] = v;
        curr[1] = head[u];
        head[u] = index++;
    }
}
